
//先表示一个节点
class Node {
    public String value;
    public Node next;
    public Node(String value) {
        this.value = value;
        this.next = null;
    }
}
public class MyLinkList {
    //头节点(没有傀儡节点)
    private Node head=null;

    //获取链表长度
    //时间复杂度O(n)
    public int size() {
        int size=0;
        for(Node cur=head;cur!=null;cur=cur.next){
            size++;
        }
        return size;
    }


    //尾插
    public void addLast(String value) {
        Node newNode=new Node(value);
        if(head==null) {
            head=newNode;
            return;
        }
        //通过循环找到尾节点
        Node tail=head;
        while(tail != null) {
            if(tail.next==null) {
                break;
            }
            tail=tail.next;
        }
        tail.next=newNode;
    }


    //头插
    public void addFirst(String value) {
        Node newNode=new Node(value);
        if(head==null) {
            head=newNode;
            return;
        }
        newNode.next=head;
        head=newNode;
    }

    //指定位置插入
    public void add(int index,String value) {
        //判断下标是否合法
        if(index<0 || index>size()) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        //针对头插
        if(index==0) {
            addFirst(value);
            return;
        }
        //针对尾插
        if(index==size()) {
            addLast(value);
            return;
        }
        //其他情况
        Node newNode=new Node(value);
        Node pre= head;
        for(int i=0;i<index-1;i++){
            pre=pre.next;
        }
        newNode.next=pre.next;
        pre.next=newNode;
    }


    //判断某个元素在链表中是否存在
    //有则返回true，无则返回false
    public boolean contains(String value){
        for(Node cur=head;cur!=null;cur=cur.next){
            if(cur.value.equals(value)){
                return true;
            }
        }
        return false;
    }


    //判断某个元素在链表中是否存在
    //有则返回索引，无则返回-1
    public int indexOf(String value) {
        int index=0;
        for(Node  cur=head;cur!=null;cur=cur.next){
            if(cur.value.equals(value)){
                return index;
            }
            index++;
        }
        return -1;
    }


    //按照下标删除
    public void remove(int index){
        //1.判断下标是否合法
        if(index<0 || index>=size()){
            return;
        }
        //2.针对头节点
        if(index==0){
            head=head.next;
            return;
        }
        //3.其他情况
        Node pre=head;
        for(int i=0;i<index-1;i++) {
            pre=pre.next;
        }
        Node toRemove=pre.next;
        pre.next=toRemove.next;
    }


    //按照值删除
    public void remove(String value) {
        //1.针对链表为空
        if(head==null){
            return;
        }
        //2.针对头节点
        if(head.value.equals(value)){
            head=head.next;
            return;
        }
        //3.其他情况
        Node pre=head;
        for(;pre!=null;pre=pre.next){
            if(pre.next!=null && pre.next.value.equals(value)){
                break;
            }
        }
        if(pre==null){
            return;
        }
        pre.next=pre.next.next;
    }


    //清空链表的所有元素
    public void clear() {
        head=null;
    }


    @Override
    public String toString() {
        StringBuilder stringBuilder=new StringBuilder();
        stringBuilder.append("[");
        for(Node cur=head;cur!=null;cur=cur.next){
            stringBuilder.append(cur.value);
            if(cur.next!=null){
                stringBuilder.append(", ");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }


    private static void test1() {
        MyLinkList list = new MyLinkList();
        list.addFirst("a");
        list.addFirst("b");
        list.addFirst("c");
        list.addFirst("d");
        System.out.println(list);
    }


    private static void test2(){
        MyLinkList list=new MyLinkList();
        list.addLast("a");
        list.addLast("b");
        list.addLast("c");
        list.addLast("d");
        System.out.println(list);
    }


    private static void test3(){
        MyLinkList list=new MyLinkList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        list.add(0,"e");
        System.out.println(list);
    }


    private static void test4(){
        MyLinkList list=new MyLinkList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        System.out.println(list);
        System.out.println(list.contains("a"));
        System.out.println(list.contains("e"));
        System.out.println(list.indexOf("a"));
        System.out.println(list.indexOf("e"));
    }

    private static void test5(){
        MyLinkList list=new MyLinkList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        System.out.println(list);
        list.remove(1);
        System.out.println(list);
        list.remove("c");
        System.out.println(list);
        list.remove(0);
        System.out.println(list);
        list.remove("a");
        System.out.println(list);
        list.remove("d");
        System.out.println(list);
    }


    public static void main(String[] args) {
        //test1();
        //test2();
        //test3();
        //test4();
        test5();
    }

}
